package mht.practice.heap;

import mht.practice.sort.SortTestHelper;

/**
 * 堆排序
 * Created by MHT on 2017/8/26.
 */
public class HeapSort {

    //我们的算法类不允许产生任何实例
    private HeapSort(){}

    // 对整个arr数组使用HeapSort排序
    // HeapSort, 将所有的元素依次添加到堆中, 在将所有元素从堆中依次取出来, 即完成了排序
    // 无论是创建堆的过程, 还是从堆中依次取出元素的过程, 时间复杂度均为O(nlogn)
    // 整个堆排序的整体时间复杂度为O(nlogn)
    public static void sort(Comparable[] arr){

        int n= arr.length;
        MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(n);
        for (int i=0;i<n;i++){
            maxHeap.insert(arr[i]);
        }
        for (int j=n-1;j>=0;j--){
            arr[j] = maxHeap.extractMax();
        }
    }

    // 测试 HeapSort
    public static void main(String[] args) {
        //测试基本数组
//        Comparable[] a = {1234,912,844,753,623,510,455,326,210,110};
//        HeapSort.sort(a);
//        for (int i=0;i<a.length;i++){
//            System.out.print(a[i]+" ");
//        }

        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("mht.practice.heap.HeapSort", arr);
    }


}
